0835. 图像重叠【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 枚举偏移

1. 📝 题目描述

• leetcode

给你两个图像 img1 和 img2，两个图像的大小都是 n x n，用大小相同的二进制正方形矩阵表示。二进制矩阵仅由若干 0 和若干 1 组成。

转换 其中一个图像，将所有的 1 向左，右，上，或下滑动任何数量的单位；然后把它放在另一个图像的上面。该转换的 重叠 是指两个图像 都 具有 1 的位置的数目。

请注意，转换 不包括 向任何方向旋转。越过矩阵边界的 1 都将被清除。

最大可能的重叠数量是多少？

---

示例 1：

输入：img1 = [
  [1, 1, 0],
  [0, 1, 0],
  [0, 1, 0]
],
img2 = [
  [0, 0, 0],
  [0, 1, 1],
  [0, 0, 1]
]

输出：3

• 解释：
  • 将 img1 向右移动 1 个单位，再向下移动 1 个单位。
  • 
  • 两个图像都具有 1 的位置的数目是 3（用红色标识）。
  • 

---

示例 2：

输入：img1 = [[1]], img2 = [[1]]
输出：1

示例 3：

输入：img1 = [[0]], img2 = [[0]]
输出：0

---

提示：

• n == img1.length == img1[i].length
• n == img2.length == img2[i].length
• 1 <= n <= 30
• img1[i][j] 为 0 或 1
• img2[i][j] 为 0 或 1

2. 🎯 s.1 - 枚举偏移

c

int largestOverlap(int** img1, int img1Size, int* img1ColSize, int** img2, int img2Size, int* img2ColSize) {
    int n = img1Size;
    int count[61][61];
    memset(count, 0, sizeof(count));
    int res = 0;
    for (int r1 = 0; r1 < n; r1++)
        for (int c1 = 0; c1 < n; c1++)
            if (img1[r1][c1])
                for (int r2 = 0; r2 < n; r2++)
                    for (int c2 = 0; c2 < n; c2++)
                        if (img2[r2][c2]) {
                            int dr = r1 - r2 + 30, dc = c1 - c2 + 30;
                            count[dr][dc]++;
                            if (count[dr][dc] > res) res = count[dr][dc];
                        }
    return res;
}

js

/**
 * @param {number[][]} img1
 * @param {number[][]} img2
 * @return {number}
 */
var largestOverlap = function (img1, img2) {
  const n = img1.length
  const pts1 = [],
    pts2 = []
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) {
      if (img1[i][j]) pts1.push([i, j])
      if (img2[i][j]) pts2.push([i, j])
    }
  const map = new Map()
  let res = 0
  for (const [r1, c1] of pts1)
    for (const [r2, c2] of pts2) {
      const key = (r1 - r2 + 30) * 61 + (c1 - c2 + 30)
      const cnt = (map.get(key) || 0) + 1
      map.set(key, cnt)
      res = Math.max(res, cnt)
    }
  return res
}

py

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        from collections import Counter
        n = len(img1)
        pts1 = [(i, j) for i in range(n) for j in range(n) if img1[i][j]]
        pts2 = [(i, j) for i in range(n) for j in range(n) if img2[i][j]]
        if not pts1 or not pts2: return 0
        cnt = Counter((r1-r2, c1-c2) for r1, c1 in pts1 for r2, c2 in pts2)
        return max(cnt.values())

• 时间复杂度：$O(n^4)$，其中 n 是矩阵边长
• 空间复杂度：$O(n^2)$

算法思路：

• 枚举两张图片中所有 1 的位置对，统计相同偏移量出现的次数
• 最大计数即为最大重叠数